# 定义PCB
import copy


#定义PCB
class PCB:
    def __init__(self):
        self.id = 0     #进程ID
        self.name = ''
        self.size = 0
        self.next = None

# 定义PCB的各种状态
running=None    #PCB的运行队列
ready = None    #PCB的就绪队列
blocked = None  #PCB的阻塞队列
q = None    #PCB类型的一个指针
p = None    #PCB类型的一个指针
id = 1
size = 0
name = ''

# 定义设备控制表
class DCT:
    def __init__(self):
        self.type=None
        self.name = ''
        self.busy = 0
        self.occupied = None    #设备状态
        self.waiting = None     #挂在设备进程队列
        self.next = None    #设备队列
        self.coct = None  # 定义上级控制器


# 定义控制器控制表
class COCT:
    def __init__(self):
        self.name = ''
        self.busy = 0
        self.occupied = None    #控制器状态
        self.waiting = None     #挂在控制器进程队列
        self.next = None        #控制器队列
        self.chct = None  # 定义控制器的上级通道


# 定义通道控制表
class CHCT:
    def __init__(self):
        self.name = ''
        self.busy = 0
        self.occupied = None    #通道状态
        self.waiting = None     #挂在通道进程队列
        self.next = None        #通道队列

#定义系统设备表
class SDT:
    def __init__(self):
        self.sdtID=0  #设备标识符
        self.type= ''   #设备类型
        self.s_total=0  #同一设备类型的总数
        self.allocation=0   #已分配数
        self.dct=None   #设备入口

#####################################################
dcts = None
cocts = None
chcts = None
sdts=[]



# 使用队列结构来模拟进程调度
# 入队,id为PCB标示，name为PCB名，size为PCB大小，head为进队列的PCB，rt为PCB资源表
def enqueue(id, name, size, head,rt):
    global PCBList
    node = PCB()
    node.next = None
    node.id = id
    node.name = name
    node.size = size
    node.rt=rt
    temp = head
    while temp.next != None:
        temp = temp.next
    temp.next = node
    PCBList.append(node)

# 出队，head为出队列的PCB
def dequeue(head):
    global PCBList
    tmp = head.next
    if head.next != None:
        head.next = head.next.next
        tmp.next = None
    # PCBList.remove(tmp)
    return tmp


###################################################################
# 通过设备名查找设备，返回设备
def findDCT(name):
    global sdts
    for i in range(len(sdts)):
        temp=sdts[i].dct
        while temp.next != None:
            temp = temp.next
            if temp.name == name:
                return temp
    return None

#在系统设备表里根据设备类型查找设备标号
def findDCTNo(type):
    global sdts
    resNo=0
    for i in range(len(sdts)):
        if sdts[i].type==type:
            return resNo
        else:
            resNo+=1
    return resNo

#根据设备类型查找系统设备表
def findSDT(type):
    global sdts
    temp=sdts
    for sdt in sdts:
        if sdt.type==type:
            return sdt
    return None

# 通过通道控制表根据通道名查找通道
def findChannel(name):
    global chcts
    temp = chcts
    while temp.next != None:
        temp = temp.next
        if temp.name == name:
            return temp
    return None


# 通过控制器控制表根据控制器名查找控制器
def findController(name):
    global cocts
    temp = cocts
    while temp.next != None:
        temp = temp.next
        if temp.name == name:
            return temp
    return None


# waiting为通道，控制器，设备上挂的PCB
def addProcesstoWaiting(waiting, p):
    temp = waiting
    while temp.next != None:
        temp = temp.next
    temp.next = PCB()
    temp.next.id = p.id
    temp.next.name = p.name
    temp.next.size = p.size
    temp.next.next = None


# 分配通道，chct为通道，p为进程
def allocateCHCT(chct, p):
    global running
    if chct.occupied != None:
        print("不能分配通道")
        addProcesstoWaiting(chct.waiting, p)
    else:
        chct.occupied = p
        print("分配成功！")


###############################################
# 分配控制器，coct为控制器，p为进程
def allocateCOCT(coct, p):
    global running, blocked, ready
    if coct.occupied != None:
        print("不能分配控制器")
        addProcesstoWaiting(coct.waiting, p)
    else:
        coct.occupied = p
        allocateCHCT(coct.chct, p)



# 释放通道，name为设备名，chct为通道，p为进程
def releaseCHCT(name, chct, p):
    if p != None:
        addProcesstoWaiting(chct.waiting, p)
    if name == chct.occupied.name:
        if chct.waiting.next != None:
            chct.occupied = dequeue(chct.waiting)
        else:
            chct.occupied = None


# 释放控制器，name为设备名，coct为控制器，p为进程
def releaseCOCT(name, coct, p):
    if p != None:
        addProcesstoWaiting(coct.waiting, p)
    if name == coct.occupied.name:
        if coct.waiting.next != None:
            coct.occupied = dequeue(coct.waiting)
        else:
            coct.occupied = None
        releaseCHCT(name, coct.chct, coct.occupied)


# 释放设备
def releaseDCT():
    global Available
    nameDCT = input("请输入要释放设备的名称:")
    nameP = input("请输入要释放的进程名称:")
    temp = findDCT(nameDCT)
    if temp == None:
        print("没有对应的设备！")
        return
    if temp.occupied.name == nameP:
        if temp.waiting.next != None:
            temp.occupied = dequeue(temp.waiting)
        else:
            temp.occupied = None
        releaseCOCT(nameP, temp.coct, temp.occupied)
        num = Available[temp.type] +1
        Available[temp.type] = num
        pcb=findPCB(nameP)
        resNo = findDCTNo(temp.type)  # 更新进程资源表
        pcb.rt.need[resNo]+=1
        pcb.rt.allocation[resNo] -= 1
    else:
        print("没有对应的设备和进程！")


# 增加通道
def addChannel(name):
    global chcts
    temp = CHCT()
    temp.name = name
    temp.next = None
    temp.busy = 0
    temp.waiting = PCB()
    temp.waiting.next = None
    temp.occupied = None
    head = chcts  # 计入chcts队列
    while head.next != None:
        head = head.next
    head.next = temp


# 增加控制器
def addController(name, chct):
    global cocts
    temp = COCT()
    temp.name = name
    temp.next = None
    temp.busy = 0
    temp.waiting = PCB()
    temp.waiting.next = None
    temp.occupied = None
    temp.chct = chct
    head = cocts  # 进入cocts队列
    while head.next != None:
        head = head.next
    head.next = temp


# 增加设备
def addDevice(type,name, coct):
    global sdts,Available
    kinds=findDCTNo(type)
    sdt=sdts[kinds]
    temp = DCT()
    temp.next = None
    temp.name=name
    temp.type=sdt.type
    temp.busy = 0
    temp.waiting = PCB()
    temp.waiting.next = None
    temp.occupied = None
    temp.coct = coct
    head=sdt.dct
    while head.next != None:
        head = head.next
    head.next = temp
    #更新系统设备表
    h=sdt.dct
    while h.next!=None:
        h=h.next
    sdt.s_total+=1

#在系统设备表里添加新的设备类型
def add_sdt():
    newSDT=input("请输入新设备类型的名称:")
    if findSDT(newSDT)!=None:
        print("该设备类型已存在，无需添加！")
        return
   # addSDT(newSDT)

# 添加设备
def add_dct():
    newDCT = input("请输入新的设备的名字:")
    newSDT=input("请输入设备类型")
    newCOCT = input("请输入要添加到的控制器的名字:")
    addDevice(newSDT,newDCT, findController(newCOCT))


# 添加控制器
def add_coct():
    newCOCT = input("请输入新控制器的名字:")
    newCHCT = input("请输入要添加到的通道的名字:")
    addController(newCOCT, findChannel(newCHCT))


# 添加通道
def add_chct():
    newCHCT = input("请输入新的通道的名字:")
    addChannel(newCHCT)


# 删除设备
def deleteDCT(nameDCT):
    global sdts
    temp = findDCT(nameDCT)
    head = temp
    if temp == None:
        print("没有对应的设备")
        return
    else:
        sdt=findSDT(temp.type)
        head=sdt.dct
    while head.next != None:
        if temp.name == head.next.name:
            DCT()
            if temp.occupied != None:
                print("此设备现在正在使用不能删除")
            else:
                SDT()
                head.next = head.next.next
                sdt.s_total=sdt.s_total-1
                Available[temp.type]= sdt.s_total
                print("成功删除该设备")
            break
        else:
            head = head.next


# 删除控制器
def deleteCOCT(nameCOCT):
    global cocts
    temp = findController(nameCOCT)
    head = cocts
    if temp == None:
        print("没有对应的控制器")
        return
    else:
        while head.next != None:
            if temp.name == head.next.name:
                if temp.occupied != None:
                    print("此控制器现在正在被使用不能删除")
                else:
                    head.next = head.next.next
                    print("成功删除该控制器")
                break
            head = head.next


# 删除通道
def deleteCHCT(nameCHCT):
    temp = findChannel(nameCHCT)
    head = chcts
    if temp == None:
        print("没有对应的通道")
        return
    else:
        while head.next != None:
            if temp.name == head.next.name:

                if temp.occupied != None:
                    print("此通道现在正在使用不能删除")
                else:
                    head.next = head.next.next
                    print("成功删除该通道")
                break
            head = head.next

#初始化系统设备表
def initSDT():
    global sdts
    sdt1=SDT()
    sdt1.sdtID=1;
    sdt1.s_total=0;
    sdt1.type= '设备A类'
    sdt1.allocation=0;
    sdt1.dct=DCT();
    sdt1.dct.next=None
    sdts.append(sdt1)

    sdt2 = SDT()
    sdt2.sdtID = 2;
    sdt2.s_total = 0;
    sdt2.type = '设备B类'
    sdt2.allocation = 0;
    sdt2.dct = DCT();
    sdt2.dct.next = None
    sdts.append(sdt2)

    sdt3 = SDT()
    sdt3.sdtID = 3;
    sdt3.s_total = 0;
    sdt3.type = '设备C类'
    sdt3.allocation = 0;
    sdt3.dct = DCT();
    sdt3.dct.next = None
    sdts.append(sdt3)

#系统资源表
sMax=[15,15,15]#系统最大资源
sAllocation = [0, 0, 0]#系统已分配资源
sAvailable = [0, 0, 0]#系统可利用资源
#银行家算法，只使用3种资源
#sMax,sAllocation,sNeed为系统资源，一维列表
#输入参数:max，allocation，need,request分别为进程最大资源，已分配资源，还需要的资源,都为二维列表
#request为当前进程请求的资源，为一维列表
#输出：返回True和False,资源分配安全为True，不安全为False
def Banker(max,allocation,request):
    global sMax,sAllocation,sAvailable

    for i in range(3):
        sum=0
        for j in range(len(max)):
            sum+=allocation[j][i]
        sAllocation[i] = sum
    for i in range(3):
        sAvailable[i]=sMax[i]-sAllocation[i]

    need=[]
    for i in range(len(max)):
        ne=[]
        for j in range(3):
            ne.append(max[i][j]-allocation[i][j])
        need.append(ne)
    pcbNum=len(max)
    for i in range(3):
        if request[i]>need[0][i]:
            print('出错！进程申请的资源多于它自己申报的最大量.')
            return False
    for i in range(3):
        if request[i]>sMax[i]-sAllocation[i]:
            print('出错！进程申请的资源现已多于剩余资源')
    Pause=[]#Pause[i]只是一个暂时寄存的中间变量，为防止在下面
			#安全性检查时修改到sAvailable[i]而代替的一维数组
    Finish=[0 for i in range(pcbNum)]
    for i in range(3):
        Pause.append(sAvailable[i])
    #预分配
    for i in range(3):
        need[0][i]-=request[i]
        allocation[0][i]+=request[i]
        Pause[i]-=request[i]
    m=pcbNum
    for g in range(m):
        for i in range(m):
            b=0
            for j in range(3):
                if need[i][j]<=Pause[j]:#检测每种资源是否满足要求
                    b=b+1
                if Finish[i]==0 and b==3:#如果每种资源都满足要求且该进程还没有Fininsh为False则进行资源分配
                    try:
                        for k in range(3):
                            Pause[i]=Pause[i]+allocation[i][k]
                        Finish[i]=1
                    except:
                        return True
    #统计Finish的个数
    num=0
    for i in Finish:
        num+=i
    if num==m:
        print('该进程申请的资源是安全的')
        print(request)
        return True
    else:
        print("该进程申请的资源是不安全的")
        print(request)
        return False

#设备请求
#输入参数：running为正在运行的进程，deviceName为设备名，state
#为True的时候请求该设备，False为释放该设备
#无输出：函数内部还自行打印设备状态
def requestDevice(running,deviceName,state):
    global sdts
    dct = findDCT(deviceName)
    if dct == None:
        print("没有该设备")
        return False
    if state:
        pcb = PCB()
        pcb.id = running.PID
        pcb.name = running.name
        if dct.occupied != None:
            print("不能分配设备")
            addProcesstoWaiting(dct.waiting, pcb)
            return False
        else:
            dct.occupied = pcb
            allocateCOCT(dct.coct, pcb)
            return True
    else:
        if dct.occupied.name == running.name:
            if dct.waiting.next != None:
                dct.occupied = dequeue(dct.waiting)
            else:
                dct.occupied = None
            releaseCOCT(running.name, dct.coct, dct.occupied)
            print(deviceName+'释放成功')
            return True
        else:
            print("没有对应的设备和进程！")
            return False


#显示设备
def displayDCT():
    global chcts, sdts, cocts
    chct = chcts
    Bus={}
    Bus['name']='Bus'
    chctList=[]
    while chct.next != None:
        chct = chct.next
        chctObject={}
        chctObject['name']=chct.name
        if chct.occupied != None:
            chctObject["occupied"]=chct.occupied.name
        else:
            chctObject["occupied"] = ""
        # waiting是头节点，pub执行队列的第一个进程
        pcb = chct.waiting.next
        CHCTwaiting=[]
        while pcb != None:
            CHCTwaiting.append(pcb.name)
            pcb = pcb.next
        chctObject["waiting"]=CHCTwaiting
        print()  # 换行
        # --------------------------------------------
        coct = cocts
        coctList = []
        while coct.next != None:
            coct = coct.next
            if coct.chct.name == chct.name:
                coctObject = {}
                coctObject["name"]=coct.name
                if coct.occupied != None:
                    coctObject['occupied']=coct.occupied.name
                else:
                    coctObject['occupied'] = ''
                pcb = coct.waiting.next
                COCTwaiting=[]
                while pcb != None:
                    COCTwaiting.append(pcb.name)
                    pcb = pcb.next
                coctObject['waiting']=COCTwaiting
                # --------------------------------------
                DCTList=[]
                for i in range(len(sdts)):
                    dct = sdts[i].dct
                    while dct.next != None:
                        dct = dct.next
                        if dct.coct.name == coct.name:
                            dctObject={}
                            dctObject['name'] =dct.name
                            if dct.occupied != None:
                                dctObject['occupied']=dct.occupied.name
                            else:
                                dctObject['occupied'] = ''
                            pcb = dct.waiting.next
                            DCTwaiting=[]
                            while pcb != None:
                                DCTwaiting.append(pcb.name)
                                pcb = pcb.next
                            dctObject['waiting']=DCTwaiting
                            DCTList.append(dctObject)
                coctObject['children']=DCTList
                coctList.append(coctObject)
        chctObject['children']=coctList
        chctList.append(chctObject)
    Bus['children']=chctList
    return Bus



#主函数
def main():
    global chcts,cocts,dcts
    initSDT()   #初始化系统设备表
    cocts = COCT()  #初始化控制器，该控制器为控制器的头指针，为便于增加和删除，不存放真正的控制器
    cocts.next = None
    chcts = CHCT()  #初始化通道，该通道为通道的头指针，为便于增加和删除，不存放真正的通道
    chcts.next = None
    addChannel("通道1")   #增加通道
    addChannel("通道2")
    addChannel("通道3")
    addController("控制器1", findChannel("通道1"))   #增加控制器，其中要传入控制器和通道，因为控制器的上级为通道
    addController("控制器2", findChannel("通道2"))
    addController("控制器3", findChannel("通道2"))

    addController("控制器4", findChannel("通道3"))
    addController("控制器5", findChannel("通道3"))
    addController("控制器6", findChannel("通道3"))

    addDevice('设备A类',"设备A1", findController("控制器1")) #增加设备，其中要传入设备和控制器，因为设备的上级为控制器
    addDevice('设备B类',"设备B1", findController("控制器2"))
    addDevice('设备B类',"设备B2", findController("控制器3"))
    addDevice('设备C类',"设备C1", findController("控制器4"))
    addDevice('设备C类',"设备C2", findController("控制器4"))
    addDevice('设备C类',"设备C3", findController("控制器5"))
    pcb1 = PCB()
    pcb1.id = 1
    pcb1.name = '进程1'
    pcb2 = PCB()
    pcb2.id = 2
    pcb2.name = '进程2'
    while 1:
            print("1:设备请求")
            print("2:设备释放")
            print("3:查看设备运行情况")
            print('4:查看系统设备表')
            print("5:添加新的设备")
            print("6:添加新的控制器")
            print("7:添加新的通道")
            print("8:删除设备")
            print("9:删除控制器")
            print("10:删除通道")
            print("11:使用银行家算法进行资源分配")
            print("0:退出")
            try:
                choice2=int(input())
            except:
                print("输入有误，请重新输入")
                continue
            if choice2==1:
                pcbNo=input("进程号:")
                deviceName=input("设备名:")
                if pcbNo==1:
                    pcb=pcb1
                else:
                    pcb=pcb2
                requestDevice(pcb,deviceName,True)
            if choice2==2:
                pcbNo = input("进程号:")
                deviceName = input("设备名:")
                if pcbNo == 1:
                    pcb = pcb1
                else:
                    pcb = pcb2
                requestDevice(pcb, deviceName, False)
            if choice2==3: displayDCT()
            if choice2==5: add_dct()
            if choice2==6: add_coct()
            if choice2==7: add_chct()
            if choice2==8:
                nameDCT = input("请输入要删除设备的名字:")
                deleteDCT(nameDCT)
            if choice2==9:
                nameCOCT = input("请输入要删除控制器的名字:")
                deleteCOCT(nameCOCT)
            if choice2==10:
                nameCHCT = input("请输入要删除通道的名字:")
                deleteCOCT(nameCHCT)
            if choice2==11:
                global sMax,sAvailable,sAllocation
                sMax=[10,5,7]
                sAvailable=[5,3,2]
                sAllocation=[5,2,5]
                max=[[9,0,2],[2,2,2],[4,3,3]]
                alloction=[[4,0,2],[2,1,1],[0,0,2]]
                need=[[5,0,0],[0,1,1],[4,3,1]]
                request=[0,0,0]
                Banker(max,alloction,need,request)
            if choice2==0:  break
if __name__ == '__main__':
    main()
